package com.yvon.service.demo.algorithm.offer;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 */
public class P38 {

    public static void main(String[] args) {
        Solution solution = new P38().new Solution();
        String[] abcs = solution.permutation("abc");
        for (int i = 0; i < abcs.length; i++) {
            System.out.print(abcs[i] + " ");
        }
        System.out.println(abcs);
    }
    /**
     * https://blog.csdn.net/CR7lmz/article/details/104211408?spm=1001.2101.3001.6650.13&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-13-104211408-blog-95939228.pc_relevant_multi_platform_featuressortv2removedup&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-13-104211408-blog-95939228.pc_relevant_multi_platform_featuressortv2removedup&utm_relevant_index=14
     */
    class Solution {
        private char[] chars;
        private List<String> res;

        public String[] permutation(String s) {
            chars = s.toCharArray();
            res = new ArrayList<>();
            dfs(0);
            return res.toArray(new String[res.size()]);
        }


        public void  dfs(int i) {
            if (i == chars.length - 1) {
                res.add(String.valueOf(chars));
                return;
            }else {
                Set<Character> set = new HashSet<>();
                for (int j = i; j < chars.length; j++) {
                    if (set.contains(chars[j])) {
                        continue;
                    }
                    set.add(chars[j]);
                    swap(i, j);
                    dfs(i + 1);
                    swap(i, j);
                }
            }
        }

        private void swap( int i, int j) {
            if (i != j) {
                char tmp = chars[i];
                chars[i] = chars[j];
                chars[j] = tmp;
            }
        }
    }
}
